package 三指针法_三路快排;

import com.alibaba.fastjson.JSON;

import java.util.Random;

public class 快速排序 {

    public static int count = 0;
    private static Random random = new Random();

    private int[] fastSort(int[] arr) {
        this.fastDg(arr, 0, arr.length - 1);
        return arr;
    }

    /**
     * 1. 获取left元素在方位内能排哪个位置,返回中间下标
     * 2. 继续除中间元素外左右递归
     */
    private void fastDg(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        /**
         * 随机选择一个与后面元素切换位置,
         * 实验得知 未交换前count=25 交换后count=16
         */
        int index = random.nextInt(right - left) + left;
        int temp = arr[left];
        arr[left] = arr[index];
        arr[index] = temp;

        //返回的元素就比一边都大,又比一边都小
        int midIndex = this.sortMidBig(arr, left, right);
        this.fastDg(arr, left, midIndex - 1);
        this.fastDg(arr, midIndex + 1, right);

    }

    /**
     * 较多可能会遇到排序好的数组,造成n^2复杂度,不好,应该随机选择基准下标
     * 因为每次都选择第一个元素,所以我可以随机选一个后面的元素与第一个元素切换位置
     */
    private int sortMidBig(int[] arr, int left, int right) {

        int tmp = arr[left];//基点

        //5,3,6,7,1,2,9
        while (left < right) {
            count++;
            //从右边先找一个比基点小的元素
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            //找到了比基点小的元素,放到左边去
            arr[left] = arr[right];
//            left++;//到位一个,这里到位+1会影响跳出循环时的赋值
            //再从左边找一个比基点大的元素
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            //找到了比基点大的元素,放到右边去
            arr[right] = arr[left];
//            right--;//到位一个
        }
        //跳出循环时,left=right
        arr[left] = tmp;
        //当前位置就是中间点,左右两边已经排序好了
        return left;
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        快速排序 n = new 快速排序();
        int[] result = n.fastSort(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
                14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34});
        System.out.println(JSON.toJSONString(result));
        System.out.println(count);
        System.out.println(System.currentTimeMillis() - startTime);
    }

}
